package binary_tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
    private List<Integer> data;
    private MaxHeap(){
        this(10);
    }
    private MaxHeap(int initCap){
        this.data=new ArrayList<>(initCap);
    }
    public MaxHeap(int[] arr){
        data=new ArrayList<>(arr.length);
        for(int i:arr){
            data.add(i);
        }
        for(int i=parent(data.size()-1);i>=0;i--){
            siftDown(i);
        }
    }
    public void add(int value){
        this.data.add(value);
        siftUp(data.size()-1);
    }
    public int extractMax(){
        if(data.size()==0){
            throw new NoSuchElementException("heap is empty!");
        }
        int max=data.get(0);
        int last=data.get(data.size()-1);
        data.set(0,last);
        data.remove(data.size()-1);
        siftDown(0);
        return max;
    }
    private void siftDown(int i){
        while(leftChild(i)<data.size()){
            int j=leftChild(i);
            if(j+1<data.size()&&data.get(j+1)>data.get(j)){
               j=j+1;
            }
            if(data.get(i)>=data.get(j)){
                break;
            }else{
                swap(i,j);
                i=j;
            }
        }
    }
    private void siftUp(int k){
        while(k>0&&data.get(k)> data.get(parent(k))){
            int parent=parent(k);
            swap(k,parent);
            k=parent;
        }
    }

    private void swap(int k, int parent) {
        int temp=data.get(k);
        data.set(k, data.get(parent));
        data.set(parent,temp);
    }

    private int parent(int k) {
        return (k-1)>>2;
    }
    private int leftChild(int k){
        return (k<<2)+1;
    }
    private int rightChild(int k){
        return (k<<2)+2;
    }
public String toString(){
        return data.toString();
}
    public static void main(String[] args) {
        int[] data={17,80,68,21,15,14,40,31,20};
        MaxHeap heap=new MaxHeap(data);
        for(int i=0;i<data.length;i++){
            data[i]=heap.extractMax();

        }
        System.out.println(Arrays.toString(data));
    }

}
